/*
 * Author:Carrie Zhao
 */
#include "stdio.h"
#include "stdlib.h"

typedef int (*compare)(const void *, const void *);

//recursively do binary search
void *recur_bsearch(const void *key, void *array, int len, int size, compare cmp_fun)
{
	//base case
	int ret = 0;
	if (len == 0)
		return NULL;
	else if ((ret = cmp_fun(array + size * (len/2), key)) == 0)
		return array + size * (len/2);
	else {
		//smaller problem;
		if (ret > 0)
			recur_bsearch(key, array, len/2, size, cmp_fun);
		else 
			recur_bsearch(key, array+size*(len/2+1), len/2, size, cmp_fun);
	}
}
void *binary_search(const void *key, void *array, int len, int size, compare cmp_fun)
{
	int start = 0, end = len, result = -1;
	
	if (!array || len == 0 || !cmp_fun) return NULL;

	while ((result = cmp_fun(array+size*((start+end)/2), key))) {
		if (end <= start) {
			//printf("return null\n");
			return NULL;
		}
		if ( result > 0 ) 
			end = (start + end)/2 -1;
		else
			start = (start + end)/2 + 1;
		if (start == len) return NULL;
		//printf("start %d, end %d\n", start, end);
	}
	return array+size*((start+end)/2);
}

int int_cmp(const void *aa, const void *bb)
{
	int a = *((int *)aa), b = *((int *)bb);
	//printf("array %d, key %d\n", a, b);
	if (a > b) 
		return 1;
	else if (a < b) 
		return -1;
	else 
		return 0;
}
int main()
{
	int i = 15, *ret = NULL;
	int a[15] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
	for (i = 0; i < 32; i++) {
		ret = (int *)binary_search((const void *)&i, (void *)a, 15, sizeof(int), int_cmp);
		if (ret)
			printf("ret = %d, i = %d\n", *ret, i);
		else 
			printf("can not find %d in array\n", i);
	}
	printf("recursive binary search\n");
	for (i = 0; i < 32; i++) {
		ret = (int *)recur_bsearch((const void *)&i, (void *)a, 15, sizeof(int), int_cmp);
		if (ret)
			printf("ret = %d, i = %d\n", *ret, i);
		else
			printf("can not find %d in array\n", i);
	}

	return 0;
}
